package chujisuanfa;

import jdk.internal.org.objectweb.asm.Handle;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    @Override
    public String toString() {
        return val +" "
                 + next ;
    }
}
public class ReverseList {
    public static ListNode reverseList(ListNode head) {
        //在头部插入结点
        if(head==null||head.next==null)
            return head;
        ListNode newHead= reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;
        if(list2==null) return list1;
        ListNode now;
        if(list1.val<=list2.val){
            now =list1;
            list1=list1.next;
        }else{
            now =list2;
            list2=list2.next;
        }

        ListNode head = now;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                now.next=list1;
                list1 = list1.next;
                now = now.next;
            }else{
                now.next=list2;
                list2 = list2.next;
                now = now.next;
            }
        }
        if(list1!=null){
            now.next=list1;
        }
        if(list2!=null){
            now.next=list2;
        }
        return head;
    }


    public static boolean isPalindrome(ListNode head){
        ListNode midle = head;
        ListNode tail = head;
        boolean flag = false;
        Stack<Integer> stack = new Stack<>();
        stack.push(midle.val);
        while(tail.next!=null){
            if (flag){
                midle=midle.next;
                stack.push(midle.val);
                tail=tail.next;
                flag=false;
            }else{
                tail=tail.next;
                flag=true;
            }
        }
        midle = midle.next;
        if(!flag) stack.pop();
        while(!stack.isEmpty()){
            int i = stack.pop();
            if(i!=midle.val) return false;
            midle=midle.next;
        }
        return true;
    }

//方法二
    private ListNode frontPointer;
    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }

    public  boolean isPalindrome2(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }

    public static boolean hasCycle(ListNode head){
        Map<ListNode,Integer> map = new HashMap();

        while(head!=null){
            if(map.containsKey(head)) return true;
            map.put(head,0);
            head=head.next;
        }
        return false;
    }


    public static void main(String[] args) {
        ListNode head = null;
        ListNode head2 = new ListNode(1,new ListNode(2,null));
        ReverseList d = new ReverseList();
        System.out.println(hasCycle(head2));


    }
}




